import java.util.Arrays;

public class 按公因数计算最大组件大小 {

    public static int MAXN = 20001;
    public static int MAXM = 100001;
    public static int[] factor = new int[MAXM]; // 下标代表的是因子, 存储的是出现的第一个 nums 的下标
    public static int[] farther = new int[MAXN];
    public static int[] size = new int[MAXN];
    public static int n;
    public int largestComponentSize(int[] nums) {
        n = nums.length;
        build();
        for (int i = 0,x; i < n; i++) {
            x = nums[i];
            for (int j = 2; j * j <= x; j++) {
                if (x % j == 0) {
                    if (factor[j] == -1) {
                        factor[j] = i;
                    } else {
                        union(i,factor[j]);
                    }
                }
                while (x % j == 0) {
                    x /= j;
                }
            }
            if (x > 1) {
                if (factor[x] == -1) {
                    factor[x] = i;
                } else {
                    union(i,factor[x]);
                }
            }
        }
        return maxSize();
    }

    public static int maxSize () {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans,size[i]);
        }
        return ans;
    }
    public static void build () {
        for (int i = 0; i <= n; i++) {
            farther[i] = i;
            size[i] = 1;
        }
        Arrays.fill(factor,-1);
    }

    public static int find (int i) {
        if (farther[i] != i) {
            farther[i] = find(farther[i]);
        }
        return farther[i];
    }

    public static void union (int a,int b) {
        int x = find(a);
        int y = find(b);
        if (x != y) {
            farther[x] = y;
            size[y] += size[x];
        }
    }

}
